Non-volatile memory is a type of memory that can retain data and information even when power is not applied. An example of non-volatile memory that is being used in a variety of applications, such as cellular phone technology, is “flash memory.” Flash memory is a form of electrically erasable programmable read-only memory (EEPROM), where data can be written in bytes and erased in blocks of memory. The blocks of memory typically range from 8 kBytes to 1 MByte in size. The cell density of flash memory devices can be very high, often as high as conventional dynamic random access memory (DRAM) cells, since in conventional flash memory a single floating gate structure is used for each memory cell. Flash memory devices also have relatively fast data access times. In the past, flash memory has been used in applications such as storing basic input/output system (BIOS) information in personal computers. However, with improvements in programming capabilities, and the continually increasing demand for persistent and low-power memory devices, the application of flash memory in many other areas has expanded very rapidly.
As previously mentioned, one such application is in cellular phones. At one time, cellular phones were only limited to voice communication. Now, cellular phones provide Internet access and web browsing capabilities, allow a user to capture and store computer graphic images, capture and playback video images, and provide personal digital assistant (PDA) capabilities. As a consequence, cellular phones need to be able to store different types of data and information. For example, whereas older cellular phones would only need to store data representing phone numbers, newer cellular phones need to store in addition to phone numbers, voice information, computer graphic images, small applications (e.g., Java applets) downloaded from the Internet, and the like.
The various data objects that must be stored by the flash memory have different characteristics. For example, data such as phone numbers are generally small segments of data having uniform length. Other data can be variable in length, such as voice information, where the amount of memory used depends on the length of voice information recorded. Data can be packetized, as in the case where data is downloaded from the Internet. Additionally, the amount of memory consumed by data such as voice information and image files can be considerable, spanning multiple blocks of flash memory. Application code, such as a Java applet, is unique in that the binary code must be stored contiguously in flash memory to allow for the code to be executed by a processor directly from the flash memory.
Flash memory, which is non-volatile, and has low operating power, is perfectly suited for data and information storage applications such as in cellular phones where conservation of power is very desirable. However, the operating characteristics of flash memory must be adapted to facilitate storage of the different types of data and information previously described.
Flash memory, although providing many of the characteristics required for applications in portable and remote (wireless) devices, have unique operational characteristics that need to be considered. For example, because of the floating gate structure of conventional flash memory cells, data cannot be simply overwritten. The memory cells must be erased prior to writing new data. Also, as previously mentioned, flash memory devices are designed to erase data in blocks of memory cells, rather than on a cell-by-cell basis. Thus, although only a portion of the memory cells of a block need to be updated, the entire block must be first erased before programming the new data. The process of erasing an entire block of memory cells and programming new data takes a relatively long time to complete, and deferring an erase operation is often desirable. Additionally, erasing the entire block is a problem, however, in the case where another portion of the memory cells of the block do not need to be updated. Another issue related to flash, and other floating gate memory devices, is that these memory cells have a limited life-cycle where repeated cycles of erasing and programming degrade memory cell performance. Eventually, the cell performance is degraded to such a degree that the memory cell can no longer be used to store data.
In an effort to facilitate the use of flash products in applications such as cellular phones, memory management software interfaces have been developed to make the management of data storage in flash devices transparent to the user. The memory management software carries out various operations in the flash memory such as managing code, data and files, reclaiming memory when insufficient erased memory is available for programming new data, and wear-leveling flash blocks to increase cycling endurance. Memory management typically includes functions to support storage of parameter data for EEPROM replacement, data streams for voice recordings and multimedia, Java applets and native code for direct execution, and packetized data downloads. In addition to these operations, the memory management software often ensures that in the event of a power loss, previously programmed data is not lost or corrupted. An example of this type of memory management software is Intel® Flash Data Integrator (FDI) software.
Although conventional flash memory management software has succeeded in increasing the flexibility of flash memory, there is still room for additional improvement. Conventional memory management software has limitations in the area of data management. For example, in some conventional flash memory management software, the memory space of a flash device is partitioned into fixed memory address ranges and either code or data is associated to each of the ranges. Once set at compile time, the range and the type of associated data cannot be changed without recompilation. Consequently, if at a later time a different partitioning between code and data is desired, the ranges defined for the two types of data cannot be modified unless software is recompiled. Additionally, although different flash memory management software perform many of the same functions, the process by which the functions are performed can be very different, with some being more efficient or faster than others.
Conventionally, data stored across multiple segments is organized hierarchically. FIG. 1 flash memory storage 100 grouped into volumes 104. As previously described, to store both programs and data, the memory storage 100 is partitioned into a code volume 106 and a data volume 108. Both the code volume 106 and the data volume 108 may comprise a number of code blocks 109 and data blocks 111. Of these, a data block 111 of the data volume 108, is shown in detail to show how multiple segment data is stored hierarchically by a conventional method. Each data block 111 comprises a group table 112 which serves as a directory for a second level of hierarchy, the sequence tables 116. Each sequence table 116 in turn serves as a directory for a number of data read/write units 120, in which data actually are stored.
Unfortunately, the hierarchical arrangement shown in FIG. 1 presents at least two concerns. First, writing data to a data read/write unit 120 not only necessitates erasing and rewriting the block or blocks of flash memory where the data read/write unit 120 resides, but also can invalidate tables in which the data read/write units 120 are indexed. In particular, in the hierarchical system shown in FIG. 1, changing data in the multiple segment data object can necessitate changing both the sequence table 116 in which the relevant data read/write units 120 are indexed, and the group table 112 in which the sequence tables 116 are indexed. Therefore, writing to a data read/write unit 120 stored in even a single flash memory block 100 may result in having to erase and rewrite not only that block, but also having to erase and rewrite other blocks 100 where the sequence table 116 and group table 112 reside. Having to rewrite not only the data read/write units 120, but also two levels of tables is both time consuming and also consumes the useful life of the flash memory cells by necessitating even more erase and write cycles.
Second, this hierarchical structure restricts the size or number of data segments that can be stored, segments that can be stored, which are fixed due to the system configuration and cannot be changed until the system configuration is changed, the software is recompiled, and the data volume is formatted again. In this hierarchical structure, there is a maximum number of entries for both a group table 112 and a sequence table 116. Accordingly, if a segment of data requires more data read/write units 120 than can be listed in a sequence table 116, or the number of read/write units 120 used fills more sequence tables 116 than can be listed in a group table 112, that element of data cannot be stored as a single data element. At the same time, if the data segments are very small, because of the maximum number of entries allowable in a sequence table 116, part of a volume may be unused because there cannot be enough table entries to point to all the separate entries to be made.
Therefore, there is a need for alternative memory management processes to allow for more flexibility in data storage in flash memory and related devices. It is to this need that the present invention is directed.